Relaxed two-coloring of cubic graphs

DOI10.1016/J.JCTB.2006.12.001MaRDI QIDQ885301zbMATH OpenOpenAlexFDO

Authors Robert Berke, Tibor Szabó

Publication date 8 June 2007

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01184434/file/dmAE0166.pdf

zbMATH Keywords

coloringsbounded degree graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Relaxed two-coloring of cubic graphs
• Deciding Relaxed Two-Colorability—A Hardness Jump
• Deciding Relaxed Two-Colourability: A Hardness Jump
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5

Cites work

• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• Bounded size components -- partitions and transversals.
• Deciding Relaxed Two-Colourability: A Hardness Jump
• On the linear k-arboricity of cubic graphs
• Partitioning into graphs with only small components
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5

Cited in

(8)

• Deciding Relaxed Two-Colorability—A Hardness Jump
• Deciding Relaxed Two-Colourability: A Hardness Jump
• Bounded transversals in multipartite graphs
• A note on 2-bisections of claw-free cubic graphs
• Splitting planar graphs of girth 6 into two linear forests with short paths
• Relaxed two-coloring of cubic graphs
• The linear 2- and 4-arboricity of complete bipartite graph \(K_{m,n}\)
• On the linear \((n - 1)\)-arboricity of \(K_{n(m)}\)

This page was built for publication: Relaxed two-coloring of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q885301)