GLORIA

GEOMAR Library Ocean Research Information Access

X

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • The Electronic Journal of Combinatorics  (4)
Material
Publisher
  • The Electronic Journal of Combinatorics  (4)
Person/Organisation
Language
Years
  • 1
    Online Resource
    Online Resource
    Bounds on the Distinguishing Chromatic Number
    The Electronic Journal of Combinatorics ; 2009
    In:  The Electronic Journal of Combinatorics Vol. 16, No. 1 ( 2009-07-24)
    Details
    In: The Electronic Journal of Combinatorics, The Electronic Journal of Combinatorics, Vol. 16, No. 1 ( 2009-07-24)
    Abstract: Collins and Trenk define the distinguishing chromatic number $\chi_D(G)$ of a graph $G$ to be the minimum number of colors needed to properly color the vertices of $G$ so that the only automorphism of $G$ that preserves colors is the identity. They prove results about $\chi_D(G)$ based on the underlying graph $G$. In this paper we prove results that relate $\chi_D(G)$ to the automorphism group of $G$. We prove two upper bounds for $\chi_D(G)$ in terms of the chromatic number $\chi(G)$ and show that each result is tight: (1) if Aut$(G)$ is any finite group of order $p_1^{i_1} p_2^{i_2} \cdots p_k^{i_k}$ then $\chi_D(G) \le \chi(G) + i_1 + i_2 \cdots + i_k$, and (2) if Aut$(G)$ is a finite and abelian group written Aut$(G) = {\Bbb Z}_{p_{1}^{i_{1}}}\times \cdots \times {\Bbb Z}_{p_{k}^{i_{k}}}$ then we get the improved bound $\chi_D(G) \le \chi(G) + k$. In addition, we characterize automorphism groups of graphs with $\chi_D(G) = 2$ and discuss similar results for graphs with $\chi_D(G)=3$.
    Type of Medium: Online Resource
    ISSN: 1077-8926
    URL: Article
    DOI: 10.37236/177
    Language: Unknown
    Publisher: The Electronic Journal of Combinatorics
    Publication Date: 2009
    detail.hit.zdb_id: 2010998-2
    SSG: 17,1
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 2
    Online Resource
    Online Resource
    Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number
    The Electronic Journal of Combinatorics ; 2013
    In:  The Electronic Journal of Combinatorics Vol. 20, No. 3 ( 2013-09-26)
    Details
    In: The Electronic Journal of Combinatorics, The Electronic Journal of Combinatorics, Vol. 20, No. 3 ( 2013-09-26)
    Abstract: Nordhaus and Gaddum proved, for any graph $G$, that $\chi(G) + \chi(\overline{G}) \leq n + 1$, where $\chi$ is the chromatic number and $n=|V(G)|$. Finck characterized the class of graphs, which we call NG-graphs, that satisfy equality in this bound. In this paper, we provide a new characterization of NG-graphs, based on vertex degrees, which yields a new polynomial-time recognition algorithm and efficient computation of the chromatic number of NG-graphs. Our motivation comes from our theorem that generalizes the Nordhaus-Gaddum theorem to the distinguishing chromatic number. For any graph $G$, $\chi_D(G) +\chi_D(\overline{G})\leq n+D(G)$. We call the set of graphs that satisfy equality in this bound NGD-graphs, and characterize the set of graphs that are simultaneously NG-graphs and NGD-graphs.
    Type of Medium: Online Resource
    ISSN: 1077-8926
    URL: Article
    DOI: 10.37236/2117
    Language: Unknown
    Publisher: The Electronic Journal of Combinatorics
    Publication Date: 2013
    detail.hit.zdb_id: 2010998-2
    SSG: 17,1
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 3
    Online Resource
    Online Resource
    The Distinguishing Chromatic Number
    The Electronic Journal of Combinatorics ; 2006
    In:  The Electronic Journal of Combinatorics Vol. 13, No. 1 ( 2006-02-15)
    Details
    In: The Electronic Journal of Combinatorics, The Electronic Journal of Combinatorics, Vol. 13, No. 1 ( 2006-02-15)
    Abstract: In this paper we define and study the distinguishing chromatic number, $\chi_D(G)$, of a graph $G$, building on the work of Albertson and Collins who studied the distinguishing number. We find $\chi_D(G)$ for various families of graphs and characterize those graphs with $\chi_D(G)$ $ = |V(G)|$, and those trees with the maximum chromatic distingushing number for trees. We prove analogs of Brooks' Theorem for both the distinguishing number and the distinguishing chromatic number, and for both trees and connected graphs. We conclude with some conjectures.
    Type of Medium: Online Resource
    ISSN: 1077-8926
    URL: Article
    DOI: 10.37236/1042
    Language: Unknown
    Publisher: The Electronic Journal of Combinatorics
    Publication Date: 2006
    detail.hit.zdb_id: 2010998-2
    SSG: 17,1
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 4
    Online Resource
    Online Resource
    Finding Balance: Split Graphs and Related Classes
    The Electronic Journal of Combinatorics ; 2018
    In:  The Electronic Journal of Combinatorics Vol. 25, No. 1 ( 2018-03-29)
    Details
    In: The Electronic Journal of Combinatorics, The Electronic Journal of Combinatorics, Vol. 25, No. 1 ( 2018-03-29)
    Abstract: A graph is a split graph if its vertex set can be partitioned into a clique and a stable set. A split graph is unbalanced if there exist two such partitions that are distinct. Cheng, Collins and Trenk (2016), discovered the following interesting counting fact: unlabeled, unbalanced split graphs on $n$ vertices can be placed into a bijection with all unlabeled split graphs on $n-1$ or fewer vertices. In this paper we translate these concepts and the theorem to different combinatorial settings: minimal set covers, bipartite graphs with a distinguished block and posets of height one.
    Type of Medium: Online Resource
    ISSN: 1077-8926
    URL: Article
    DOI: 10.37236/7091
    Language: Unknown
    Publisher: The Electronic Journal of Combinatorics
    Publication Date: 2018
    detail.hit.zdb_id: 2010998-2
    SSG: 17,1
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...