Relaxed two-coloring of cubic graphs

DOI10.1016/j.jctb.2006.12.001zbMath1118.05029OpenAlexW1994982407MaRDI QIDQ885301

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

bounded degree graphscolorings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (6)

Bounded transversals in multipartite graphs ⋮ On the linear \((n - 1)\)-arboricity of \(K_{n(m)}\) ⋮ Deciding Relaxed Two-Colourability: A Hardness Jump ⋮ A note on 2-bisections of claw-free cubic graphs ⋮ The linear 2- and 4-arboricity of complete bipartite graph \(K_{m,n}\) ⋮ Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths

Cites Work

• Unnamed Item
• Unnamed Item
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
• On the linear \(k\)-arboricity of cubic graphs
• Bounded size components -- partitions and transversals.
• Partitioning into graphs with only small components
• Deciding Relaxed Two-Colourability: A Hardness Jump

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