On t-relaxed 2-distant circular coloring of graphs

DOI10.1007/S40840-020-01037-ZMaRDI QIDQ2045235zbMATH OpenOpenAlexFDO

Authors Dan He, Wensong Lin

Publication date 12 August 2021

Published in Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

2-distant coloring\(t\)-relaxed 2-distant circular coloringcircular coloringdefective circular coloringNP-completenessouterplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Programming involving graphs or networks (90C35)

Abstract: Let $k$ be an positive integer. For any two integers $i$ and $j$ in $0,1,dots,k-1$, let $|i-j{|}_k=min|i-j|,k-|i-j|$ be the circular distance between $i$ and $j$. Let $t$ be a nonnegative integer. Suppose $f$ is a mapping from $V(G)$ to $0,1,dots,k-1$. If adjacent vertices receive different integers, and for each vertex $u$ of $G$, the number of neighbors $v$ of $u$ with $|f(u)-f(v){|}_k=1$ is at most $t$, then $f$ is called a $t$-relaxed 2-distant circular $k$-coloring, or simply a $(frack2,t{)}^{\ast }$-coloring of $G$. If $G$ has a $(frack2,t{)}^{\ast }$-coloring, then $G$ is called $(frack2,t{)}^{\ast }$-colorable. In this paper, we prove that, for any two fixed integers $k$ and $t$ with $kgeq2$ and $tgeq1$, deciding whether $G$ is $(frack2,t{)}^{\ast }$-colorable is NP-complete expect the case $k=2$ and the case $k=3$ and $tleq3$, which are polynomially solvable. For any outerplanar graph $G$, e show that all outerplanar graphs are $(frac52,4{)}^{\ast }$-colorable, we prove that there is no fixed positive integer $t$ such that all outerplanar graphs are $(frac42,t{)}^{\ast }$-colorable.

Recommendations

• Channel assignment problem and relaxed 2-distant coloring of graphs
• Distance Coloring
• Clique-relaxed graph coloring
• scientific article; zbMATH DE number 1833073
• Deciding Relaxed Two-Colourability: A Hardness Jump

Cites work

• \(L(h,1)\)-labeling subclasses of planar graphs
• A note on defective colorings of graphs in surfaces
• A note on the star chromatic number
• A polynomial-time nearly-optimal algorithm for an edge coloring problem in outerplanar graphs
• Channel assignment problem and relaxed 2-distant coloring of graphs
• Circular chromatic number: A survey
• Defective coloring revisited
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Extremal results on defective colorings of graphs
• Fractional, circular, and defective coloring of series-parallel graphs
• Graph theory
• scientific article; zbMATH DE number 6509339 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1933261 (Why is no real title available?)
• scientific article; zbMATH DE number 1833073 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Improper coloring of unit disk graphs
• On \((s,t)\)-relaxed \(L(1,1)\)-labelling of trees
• On (s,t)-relaxed L(2,1)-labeling of graphs
• On \((s,t)\)-relaxed strong edge-coloring of graphs
• Relaxed chromatic numbers of graphs
• Relaxed game chromatic number of graphs
• Some simplified NP-complete graph problems
• Star chromatic number

Cited in

(3)

• Channel assignment problem and relaxed 2-distant coloring of graphs
• On t-relaxed chromatic number of r-power paths
• Deciding Relaxed Two-Colorability—A Hardness Jump

This page was built for publication: On \(t\)-relaxed 2-distant circular coloring of graphs

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