|
Subcoloring
In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques. That is, each color class should form a cluster graph. The subchromatic number χS(''G'') of a graph ''G'' is the fewest colors needed in any subcoloring of ''G''. Subcoloring and subchromatic number were introduced by . Every proper coloring and cocoloring of a graph are also subcolorings, so the subchromatic number of any graph is at most equal to the cochromatic number, which is at most equal to the chromatic number. Subcoloring is as difficult to solve exactly as coloring, in the sense that (like coloring) it is NP-complete. More specifically, the problem of determining whether a planar graph has subchromatic number at most 2 is NP-complete, even if it is a * triangle-free graph with maximum degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical lat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Subcoloring Graph
In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques. That is, each color class should form a cluster graph. The subchromatic number χS(''G'') of a graph ''G'' is the fewest colors needed in any subcoloring of ''G''. Subcoloring and subchromatic number were introduced by . Every proper coloring and cocoloring of a graph are also subcolorings, so the subchromatic number of any graph is at most equal to the cochromatic number, which is at most equal to the chromatic number. Subcoloring is as difficult to solve exactly as coloring, in the sense that (like coloring) it is NP-complete. More specifically, the problem of determining whether a planar graph has subchromatic number at most 2 is NP-complete, even if it is a * triangle-free graph with maximum degree 4 , * comparability graph with maximum degree 4 , * line graph of a bipartite graph with maximum degree 4 , * graph with girth ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Comparability Graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order. Definitions and characterization For any strict partially ordered set , the comparability graph of is the graph of which the vertices are the elements of and the edges are those pairs of elements such that . That is, for a partially ordered set, take the directed acyclic graph, apply transitive closure, and remove orientation. Equivalently, a comparability graph is a graph that has a transitive orientation, an assignment of directions to the edges of the graph (i.e. an orientation of the graph) such that the adjacency relation of the resulting directe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Electronic Journal Of Combinatorics
The ''Electronic Journal of Combinatorics'' is a peer-reviewed open access scientific journal covering research in combinatorial mathematics. The journal was established in 1994 by Herbert Wilf (University of Pennsylvania) and Neil Calkin (Georgia Institute of Technology). The Electronic Journal of Combinatorics is a founding member of the Free Journal Network. According to the ''Journal Citation Reports'', the journal had a 2017 impact factor of 0.762. Editors-in-chief Current The current editors-in-chief are: * Maria Axenovich, Karlsruhe Institute of Technology, Germany * Miklós Bóna, University of Florida, United States * Julia Böttcher, London School of Economics, United Kingdom * Richard A. Brualdi, University of Wisconsin, Madison, United States * Eric Fusy, CNRS/LIX, École Polytechnique, France * Catherine Greenhill, UNSW Sydney, Australia * Brendan McKay, Australian National University, Australia * Bojan Mohar, Simon Fraser University, Canada * Marc Noy, Universitat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SIAM Journal On Discrete Mathematics
'' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was established in 1988, along with the ''SIAM Journal on Matrix Analysis and Applications'', to replace the ''SIAM Journal on Algebraic and Discrete Methods''. The journal is indexed by ''Mathematical Reviews'' and Zentralblatt MATH. Its 2009 MCQ was 0.57. According to the ''Journal Citation Reports'', the journal has a 2016 impact factor of 0.755. Although its official ISO abbreviation is ''SIAM J. Discrete Math.'', its publisher and contributors frequently use the shorter abbreviation ''SIDMA''. References External links * Combinatorics journals Publications established in 1988 English-language journals Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way ana ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete Mathematics (journal)
''Discrete Mathematics'' is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications. It was established in 1971 and is published by North-Holland Publishing Company. It publishes both short notes, full length contributions, as well as survey articles. In addition, the journal publishes a number of special issues each year dedicated to a particular topic. Although originally it published articles in French and German, it now allows only English language articles. The editor-in-chief is Douglas West ( University of Illinois, Urbana). History The journal was established in 1971. The very first article it published was written by Paul Erdős, who went on to publish a total of 84 papers in the journal. Abstracting and indexing The journal is abstracted and indexed in: According to the ''Journal Citation Reports'', the journal has a 2020 impact factor of 0.87. Notable publications * The 1972 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Permutation Graph
In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation (up to permutation symmetry) if it is prime with respect to the modular decomposition. Definition and characterization If \rho = (\sigma_1,\sigma_2,...,\sigma_n) is any permutation of the numbers from 1 to n, then one may define a permutation graph from \sigma in which there are n vertices v_1, v_2, ..., v_n, and in which there is an edge v_i v_j for any two indices i and j for which i\sigma_j. That is, two indices i and j determine an edge in the permutation graph exactly when they determine an inversion in the permutatio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Interval Graph
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. Interval graphs are chordal graphs and perfect graphs. They can be recognized in linear time, and an optimal graph coloring or maximum clique in these graphs can be found in linear time. The interval graphs include all proper interval graphs, graphs defined in the same way from a set of unit intervals. These graphs have been used to model food webs, and to study scheduling problems in which one must select a subset of tasks to be performed at non-overlapping times. Other applications include assembling contiguous subsequences in DNA mapping, and temporal reasoning. Definition An interval graph is an undirected graph formed from a family of intervals :S_i,\quad i=0,1,2,\dots by creating one vertex for each interval , and connecting two ver ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cograph
In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes ''K''1 and is closed under complementation and disjoint union. Cographs have been discovered independently by several authors since the 1970s; early references include , , , and . They have also been called D*-graphs, hereditary Dacey graphs (after the related work of James C. Dacey Jr. on orthomodular lattices), and 2-parity graphs. They have a simple structural decomposition involving disjoint union and complement graph operations that can be represented concisely by a labeled tree, and used algorithmically to efficiently solve many problems such as finding the maximum clique that are hard on more general graph classes. Special cases of the cographs include the complete graphs, complete bipartite graphs, cluster gr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Girth (graph Theory)
In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (that is, it is a forest), its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free. Cages A cubic graph (all vertices have degree three) of girth that is as small as possible is known as a -cage (or as a -cage). The Petersen graph is the unique 5-cage (it is the smallest cubic graph of girth 5), the Heawood graph is the unique 6-cage, the McGee graph is the unique 7-cage and the Tutte eight cage is the unique 8-cage. There may exist multiple cages for a given girth. For instance there are three nonisomorphic 10-cages, each with 70 vertices: the Balaban 10-cage, the Harries graph and the Harries–Wong graph. Image:Petersen1 tiny.svg, The Petersen graph has a girth of 5 Image:Heawood_Graph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bipartite Graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the ''parts'' of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets U and V may be thought of as a coloring of the graph with two colors: if one colors all nodes in U blue, and all nodes in V red, each edge has endpoints of differing colors, as is required in the graph coloring problem.. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color. One often writes G=(U,V,E) to denote a bipartite graph whose partition has the parts U and V, with E denoting ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Line Graph
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every two edges in that have a vertex in common, make an edge between their corresponding vertices in . The name line graph comes from a paper by although both and used the construction before this. Other terms used for the line graph include the covering graph, the derivative, the edge-to-vertex dual, the conjugate, the representative graph, and the θ-obrazom, as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph., p. 71. proved that with one exceptional case the structure of a connected graph can be recovered completely from its line graph. Many other properties of line graphs follow by translating the properties of the underlying graph from vertices into edges, and by Whitney's theorem the same t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
