A note on orientation and chromatic number of graphs

被引：0

作者：

Manouchehr Zaker

机构：

[1] Institute for Advanced Studies in Basic Sciences,Department of Mathematics

来源：

Journal of Combinatorial Optimization | 2017年 / 34卷

关键词：

Graph coloring; Chromatic number; Acyclic orientation; Degenerate subgraph; 05C15; 05C20;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

Let D be any edge orientation of a graph G. We denote by Δk(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta _k(D)$$\end{document} the maximum value t for which there exists a directed path v1,…,vk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v_1, \ldots , v_k$$\end{document} such that dout(vk)=t\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d^{out}(v_k)=t$$\end{document}, where dout(vk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d^{out}(v_k)$$\end{document} is the out-degree of vk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v_k$$\end{document} in D. We first obtain some bounds for the chromatic number of G in terms of Δk(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta _k(D)$$\end{document} and then show a relationship between Δk(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta _k(D)$$\end{document} and vertex partitions of a graph into degenerate subgraphs.

引用

页码：605 / 611

页数：6

共 17 条

[1]

Alon N(1992)Colorings and orientations of graphs Combinatorica 12 125-134

[2]

Tarsi M(1999)Generating all the acyclic orientations of an undirected graph Inf Process Lett 72 71-74

[3]

Barbosa VC(1979)Acyclic orientations of a graph and chromatic and independence numbers J Comb Theory Ser B 26 101-110

[4]

Szwarcfiter JL(2008)Acyclic orientations with path constraints RAIRO Oper Res 42 455-467

[5]

Deming RW(2009)Decomposing a planar graph of girth J Comb Theory Ser B 99 674-684

[6]

Figueiredo RMV(1953) into an independent set and a forest Ann of Math 58 573-580

[7]

Barbosa VC(1967)Solutions of irreflexive relations Rev Fr Autom Inf Rech Opér sér Rouge 1 127-132

[8]

Maculan N(1962)Nombre chromatique et plus longs chemins d’un graphe Dokl Akad Nauk SSSR 147 758-759

[9]

de Souza CC(2006)Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix (Russian) Discret Math 306 1207-1216

[10]

Kawarabayashi K(2008)Partition the vertices of a graph into one independent set and one acyclic set J Gr Theory 58 110-122

← 1 2 →