EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 58 / No 3 (May-June 2024) RAIRO-Oper. Res., 58 3 (2024) 2055-2073 References
Open Access
Issue
RAIRO-Oper. Res.
Volume 58, Number 3, May-June 2024
Page(s) 2055 - 2073
DOI https://doi.org/10.1051/ro/2024068
Published online 06 May 2024
  • J. Balogh, F.C. Clemen and L. Mattos, Counting r-graphs without forbidden configurations. J. Comb. Theory Ser. B 157 (2022) 216–234. [CrossRef] [Google Scholar]
  • A. Björklund, T. Husfeldt and M. Kolvisto, Set partitioning via inclusion-exclusion. SIAM J. Comput. 39 (2009) 546–563. [CrossRef] [MathSciNet] [Google Scholar]
  • D. Blanuša, Problem četiriju boja. Glasnik. Mat. Fiz. Astr. Ser. II 1 (1946) 31–42. [Google Scholar]
  • G. Brinkmann, J. Goedgebeur, J. H¨agglund and K. Markström, Generation and Properties of Snarks. Vol. 103 (2012). [Google Scholar]
  • W.G. Brown, P. Erdős and V.T. Sós, Some extremal problems on r-graphs. In New Directions in the Theory of Graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971). Academic Press, New York (1973) 53–63. [Google Scholar]
  • L. Cai and J.A. Ellis, NP-completeness of edge-colouring some restricted graphs. Discrete Appl. Math. 30 (1991) 15–27. [CrossRef] [MathSciNet] [Google Scholar]
  • A.G. Chetwynd and A.J.W. Hilton, The chromatic index of graphs of even order with many edges. J. Graph Theory 8 (1984) 463–470. [CrossRef] [MathSciNet] [Google Scholar]
  • A.G. Chetwynd and A.J.W. Hilton, Regular graphs of high degree are 1-factorizable. Proc. London Math. Soc. 3 (1985) 193–206. [CrossRef] [Google Scholar]
  • A.G. Chetwynd and A.J.W. Hilton, Star multigraphs with three vertices of maximum degree. Math. Proc. Cambridge Philos. Soc. 100 (1986) 303–317. [CrossRef] [MathSciNet] [Google Scholar]
  • A.G. Chetwynd and A.J.W. Hilton, The edge-chromatic class of graphs with maximum degree at least |V| − 3. Ann. Discrete Math. 41 (1989) 91–110. [CrossRef] [Google Scholar]
  • M. Chladný and M. Škoviera, Factorisation of snarks. Electron. J. Comb. 17 (2010) R32. [CrossRef] [Google Scholar]
  • C. De Simone and A. Galluccio, Edge-colouring of regular graphs of large degree. Theor. Comput. Sci. 389 (2007) 91–99. [CrossRef] [Google Scholar]
  • C. De Simone and A. Galluccio, Edge-colouring of join of regular graphs. J. Comb. Optim. 18 (2009) 417–428. [CrossRef] [MathSciNet] [Google Scholar]
  • B. Descartes, Network-colourings. Math. Gaz. 32 (1948) 67–69. [CrossRef] [Google Scholar]
  • R. Diestel, Graph Theory, 4th edition. Springer (2010). [Google Scholar]
  • J. Edmonds, Paths, trees, and flowers. Can. J. Math. 17 (1965) 449–467. [CrossRef] [Google Scholar]
  • J. Edmonds, Matching polytope and a polyhedron with 0, 1 vertices. J. Res. Natl. Bur. Standards B (Math. Math. Phys.) 69B (1965) 125–130. [CrossRef] [Google Scholar]
  • L. Esperet, F. Kardoš, A.D. King, D. Král and S. Norine, Exponentially many perfect matchings in cubic graphs. Adv. Math. 227 (2011) 1646–1664. [CrossRef] [MathSciNet] [Google Scholar]
  • J. Folkman and D.R. Fulkerson, Edge colorings in bipartite graphs. Comb. Math. Appl. (1969) 561–577. [Google Scholar]
  • E. Galby, P.T. Lima, D. Paulusma and B. Ries, Classifying k-edge colouring for H-free graphs. Inf. Process. Lett. 146 (2019) 39–43. [CrossRef] [Google Scholar]
  • M. Gardner, Mathematical games. Sci. Am. 4 (1976) 126–130. [CrossRef] [Google Scholar]
  • L.G.S. Gonzaga, J.B. Sousa Cruz, C.N. Silva and S.M. Almeida, The overfull conjecture on split-comparability and split-interval graphs. Discrete Appl. Math. 340 (2023) 228–238. [CrossRef] [MathSciNet] [Google Scholar]
  • A.J.W. Hilton and P.D. Johnson, Graphs which are vertex-critical with respect to the edge-chromatic number. Math. Proc. Cambridge Philos. Soc. 102 (1987) 103–112. [CrossRef] [MathSciNet] [Google Scholar]
  • D.G. Hoffman and C.A. Rodger, The chromatic index of complete multipartite graphs. J. Graph Theory 16 (1992) 159–163. [CrossRef] [MathSciNet] [Google Scholar]
  • D.A. Holton and J. Sheehan, The Petersen Graph. Cambridge University Press (1993). [CrossRef] [Google Scholar]
  • I. Holyer, The NP-completeness of edge-colouring. SIAM J. Comput. 10 (1981) 718–720. [CrossRef] [MathSciNet] [Google Scholar]
  • R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait-colorable. Amer. Math. Monthly 82 (1975) 221–239. [CrossRef] [MathSciNet] [Google Scholar]
  • R. Isaacs, Loupekine’s snarks: A bifamily of non-Tait-colorable graphs, Technical Report 263, The Johns Hopkins University (1976). [Google Scholar]
  • F. Jaeger, A survey of the cycle double cover conjecture. In Annals of Discrete Mathematics 27 – Cycles in Graphs, Vol. 27 of North-Holland Mathematics Studies (1985) 1–12. [Google Scholar]
  • A.B. Kempe, A memoir on the theory of mathematical form. Philos. Trans. R. Soc. 177 (1886) 1–70. [CrossRef] [Google Scholar]
  • M. Kochol, Superpositions and constructions of graphs without nowhere-zero k-flows. Eur. J. Comb. 23 (2002) 281–306. [CrossRef] [Google Scholar]
  • D. Kőnig, Graphok és alkalmazásuk a determinánsok és a halmazok elméletére. Math. Természettudományi Értesito 34 (1916) 104–119. [Google Scholar]
  • D.P. Koreas, The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3. J. Appl. Math. Comput. 93 (1997) 13–17. [CrossRef] [Google Scholar]
  • D. Leven and Z. Galil, NP-completeness of finding the chromatic index of regular graphs. J. Algorithms 4 (1983) 35–44. [CrossRef] [MathSciNet] [Google Scholar]
  • L. Lovász, Matching structure and the matching lattice. J. Comb. Theory Ser. B 42 (1987) 187–222. [CrossRef] [Google Scholar]
  • Y. Ma, D. Mattiolo, E. Steffen and I.H. Wolf, Pairwise disjoint perfect matchings in r-edge-connected r-regular graphs. SIAM J. Discrete Math. 37 (2023) 1548–1565. [CrossRef] [MathSciNet] [Google Scholar]
  • R.C.S. Machado and C.M.H. Figueiredo, Decompositions for edge-coloring join graphs and cobipartite graphs. Discrete Appl. Math. 158 (2010) 1336–1342. [CrossRef] [MathSciNet] [Google Scholar]
  • J. Meidanis, Edge coloring of cycle powers is easy (1998). Unpublished manuscript. URL: http://www.ic.unicamp.br/~meidanis/research/edge/cpowers.ps. [Google Scholar]
  • G.H.J. Meredith, Regular n-valent n-connected nonHamiltonian non-n-edge-colorable graphs. J. Comb. Theory Ser. B 14 (1973) 55–60. [CrossRef] [Google Scholar]
  • D. Naddef and W.R. Pulleyblank, Matchings in regular graphs. Discrete Math. 34 (1981) 283–291. [CrossRef] [MathSciNet] [Google Scholar]
  • T. Niessen, How to find overfull subgraphs in graphs with large maximum degree. Discrete Appl. Math. 51 (1994) 117–125. [CrossRef] [MathSciNet] [Google Scholar]
  • T. Niessen, How to find overfull subgraphs in graphs with large maximum degree, II. Electron. J. Comb. 8 (2001). [Google Scholar]
  • T. Nishizeki and K. Kashiwagi, An upper bound on the chromatic index of multigraphs, edited by Y. Alavi, G. Chartrand, D.R. Lick, C.E. Wall and L. Lesniak. In: Graph Theory with Applications to Algorithms and Computer Science. Wiley, New York (1985) 595–604. [Google Scholar]
  • Z.C. Ortiz, N. Maculan and J.L. Szwarcfiter, Characterizing and edge-colouring split-indifference graphs. Discrete Appl. Math. 82 (1998) 209–217. [CrossRef] [MathSciNet] [Google Scholar]
  • M.W. Padberg and M.R. Rao, Odd minimum cut-sets and b-matching. Math. Oper. Res. 7 (1982) 67–80. [CrossRef] [MathSciNet] [Google Scholar]
  • L. Perkovic and B. Reed, Edge coloring regular graphs of high degree. Discrete Appl. Math. 165/166 (1997) 567–578. [Google Scholar]
  • J. Petersen, Die theorie der regulren graphs. Acta Math. 15 (1891) 193–220. [CrossRef] [MathSciNet] [Google Scholar]
  • J. Petersen, Sur le théorème de Tait. L’Intermédiaire des Mathématiciens 5 (1898) 225–227. [Google Scholar]
  • M.J. Plantholt, The chromatic index of graphs with a spanning star. J. Graph Theory 5 (1981) 45–53. [CrossRef] [MathSciNet] [Google Scholar]
  • R. Rizzi, Indecomposable r-graphs and some other counterexamples. J. Graph Theory 32 (1999) 1–15. [CrossRef] [MathSciNet] [Google Scholar]
  • R.W. Robinson and N.C. Wormald, Almost all regular graphs are hamiltonian. Random Struct. Algor. 5 (1994) 363–374. [CrossRef] [Google Scholar]
  • P.D. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. London Math. Soc. 38 (1979) 423–460. [CrossRef] [Google Scholar]
  • P.D. Seymour, Some unsolved problems on one-factorizations of graphs, edited by J.A. Bondy and U.S.R. Murty. In: Graph Theory and Related Topics. Academic Press, New York (1979) 367–368. [Google Scholar]
  • Z. Skupień, Exponentially many hypohamiltonian snarks. Electron. Notes Discrete Math. 28 (2007) 417–424. [CrossRef] [Google Scholar]
  • G. Szekeres, Polyhedral decompositions of cubic graphs. Bull. Aust. Math. Soc. 8 (1973) 367–387. [CrossRef] [Google Scholar]
  • P.G. Tait, On the colouring of maps. Proc. R. Soc. Edinb. Sect. A 10 (1880) 501–503. [CrossRef] [Google Scholar]
  • É.A. Vieira, Grafos d-snarks, Undergraduate thesis, Federal University of Fronteira Sul (2019). [Google Scholar]
  • V.G. Vizing, On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Anal. 3 (1964) 25–30. [Google Scholar]
  • V.G. Vizing, Critical graphs with a given chromatic class (in Russian). Diskret. Anal. 5 (1965) 9–17. [Google Scholar]
  • L.M. Zatesko and E.A. Vieira, P = NP or 5-snarks exist. In Proc. 3rd Workshop de Pesquisa em Computaçã ¸ o dos Campos Gerais (WPCCG ’19). Ponta Grossa, Brazil (2019) 135–140. [Google Scholar]
  • L.M. Zatesko, R. Carmo, A.L.P. Guedes, A. Zorzi, R.C.S. Machado and C.M.H. Figueiredo, On the chromatic index of complementary prisms. In Proc. X European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB ’19), Vol. 88 of Acta Math. Univ. Comenianae. Bratislava (2019) 1071–1077. [Google Scholar]
  • L.M. Zatesko, A. Zorzi, R. Carmo and A.L.P. Guedes, Edge-colouring graphs with bounded local degree sums. Discrete Appl. Math. 281 (2020) 268–283. [CrossRef] [MathSciNet] [Google Scholar]
  • A. Zorzi and L.M. Zatesko, On the chromatic index of join graphs and triangle-free graphs with large maximum degree. Discrete Appl. Math. 245 (2018) 183–189. [CrossRef] [MathSciNet] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.