Circular backbone colorings: on matching and tree backbones of planar graphs

DOI10.1016/J.DAM.2018.05.037MaRDI QIDQ1627845zbMATH OpenOpenAlexWikidataFDO

Authors Y. Aharonov

Publication date 3 December 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.05958

zbMATH Keywords

circular backbone coloringgraph coloringmatchingplanar graphSteinberg's conjecture

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: Given a graph $G$, and a spanning subgraph $H$ of $G$, a circular $q$-backbone $k$-coloring of $(G,H)$ is a proper $k$-coloring $c$ of $G$ such that $qlelvertc(u)-c(v)vertlek-q$, for every edge $uvinE(H)$. The circular $q$-backbone chromatic number of $(G,H)$, denoted by $CB{C}_q(G,H)$, is the minimum integer $k$ for which there exists a circular $q$-backbone $k$-coloring of $(G,H)$. The Four Color Theorem implies that whenever $G$ is planar, we have $CB{C}_2(G,H)le8$. It is conjectured that this upper bound can be improved to 7 when $H$ is a tree, and to 6 when $H$ is a matching. In this work, we show that: 1) if $G$ is planar and has no $C_4$ as subgraph, and $H$ is a linear spanning forest of $G$, then $CB{C}_2(G,H)leq7$; 2) if $G$ is a plane graph having no two 3-faces sharing an edge, and $H$ is a matching of $G$, then $CB{C}_2(G,H)leq6$; and 3) if $G$ is planar and has no $C_4$ nor $C_5$ as subgraph, and $H$ is a mathing of $G$, then $CB{C}_2(G,H)leq5$. These results partially answer questions posed by Broersma, Fujisawa and Yoshimoto (2003), and by Broersma, Fomin and Golovach (2007). It also points towards a positive answer for the Steinberg's Conjecture.

Recommendations

• Steinberg-like theorems for backbone colouring
• Steinberg-like theorems for backbone colouring
• (Circular) backbone colouring: forest backbones in planar graphs
• Backbone coloring of graphs with galaxy backbones
• Backbone coloring of planar graphs without special circles

Cites work

• (Circular) backbone colouring: forest backbones in planar graphs
• -backbone colorings along pairwise disjoint stars and matchings
• Backbone colorings for graphs: Tree and path backbones
• Backbone colorings for networks.
• Backbone colouring: tree backbones with small diameter in planar graphs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Graph theory
• scientific article; zbMATH DE number 434910 (Why is no real title available?)
• List circular backbone colouring
• Models and solution techniques for frequency assignment problems
• Steinberg's conjecture is false
• Steinberg-like theorems for backbone colouring

Cited in

(5)

• (Circular) backbone colouring: forest backbones in planar graphs
• scientific article; zbMATH DE number 6178933 (Why is no real title available?)
• Steinberg-like theorems for backbone colouring
• Backbone coloring of graphs with galaxy backbones
• Backbone coloring of graphs with galaxy backbones

Describes a project that uses

Uses Software

• CALMA

This page was built for publication: Circular backbone colorings: on matching and tree backbones of planar graphs

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